package io.github.hadyang.leetcode.offer;

import io.github.hadyang.leetcode.ListNode;

/** @author haoyang.shi */
public class EntryNodeOfLoop {

  public ListNode EntryNodeOfLoop(ListNode pHead) {
    if (pHead == null || pHead.next == null) return null;

    ListNode fast = pHead, slow = pHead;

    while (fast.next != null) {
      slow = slow.next;
      fast = fast.next.next;

      if (fast == slow) break;
    }

    if (fast != slow) return null;

    ListNode cursor = pHead;
    while (cursor != fast) {
      cursor = cursor.next;
      fast = fast.next;
    }

    return cursor;
  }
}
